#include<stdio.h>


struct ElemType{
	int key;
};

void MerSort(ElemType A[], int low, int high, ElemType Aux[]);
void Mer(ElemType A[], int low, int m, int high, ElemType Aux[]);

int main(){
	ElemType A[5] = {{2},{1},{6},{4},{9}};
	ElemType Aux[5];
	MerSort(A, 0, 4, Aux);
	for(int i=0;i<=4;i++){
		printf("%d\n", A[i]);
	}
	
	ElemType B[10000];
	ElemType D_Aux[10000];
	for(int i=0;i<=9999;i++){
		B[i].key = i % 1000 + i * 2 - i % 10;
	}
	MerSort(A, 0, 9999, D_Aux);
	for(int i=0;i<=9999;i++){
		printf("%d\n", B[i]);
	}
	
}
void MerSort(ElemType A[], int low, int high, ElemType Aux[]){
	int m;
	if(low >= high){
		return;
	}
	m = (low+high)/2;
	MerSort(A, low, m, Aux);
	MerSort(A, m+1, high, Aux);
	Mer(A, low, m, high, Aux);
	for(int i=low; i<=high; ++i){
		A[i] = Aux[i];
	}
}
void Mer(ElemType A[], int low, int m, int high, ElemType Aux[]){
	int i = low;
	int j = m+1;
	int k = i;
	while(i <= m && j <= high){
		if(A[i].key <= A[j].key){
			Aux[k++] = A[i++];
		}else{
			Aux[k++] = A[j++];
		}
	}
	while(i <= m) Aux[k++] = A[i++];
	while(j <= high) Aux[k++] = A[j++];
}


